package com.cg.leetcode;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 76.最小覆盖子串
 *
 * @program: LeetCode->LeetCode_76
 * @author: cg
 * @create: 2022-04-15 21:24
 **/
public class LeetCode_76 {

    @Test
    public void test76() {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }

    /**
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * <p>
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * <p>
     * 示例 1：
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * <p>
     * 示例 2：
     * 输入：s = "a", t = "a"
     * 输出："a"
     * <p>
     * 示例 3:
     * 输入: s = "a", t = "aa"
     * 输出: ""
     * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
     * 因此没有符合条件的子字符串，返回空字符串。
     * <p>
     * 提示：
     * 1 <= s.length, t.length <= 105
     * s 和 t 由英文字母组成
     * <p>
     * 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        // window为当前窗口，need为子串各个字符的个数
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            // 统计将子串各个字符个数
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }
        // valid为满足的字符个数，start为最小字串的起始，len为最小字串的长度
        int left = 0, right = 0, valid = 0, len = Integer.MAX_VALUE, start = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 右移
            right++;
            // 当前字符是字串需要的字符，修改窗口中的字符数量
            if (need.containsKey(ch)) {
                // 更新窗口中该字符的数量
                window.put(ch, window.getOrDefault(ch, 0) + 1);
                // 其中一个字符的数量已满足
                if (need.get(ch).equals(window.get(ch))) {
                    valid++;
                }
            }
            // 所有的字符都已满足，开始缩小窗口
            while (valid == need.size()) {
                // 更新最小子串
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                char d = s.charAt(left);
                // 右移
                left++;
                // 子串中存在该字符
                if (need.containsKey(d)) {
                    // 窗口存在该字符的数量与所需的数量相等，有效字符数减一
                    if (need.get(d).equals(window.get(d))) {
                        valid--;
                    }
                    // 更新窗口中该字符的数量
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 若len长度不变，说明s中没有满足t的字符，否则直接输出start到start+len位置的子字符串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

}
